/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/implement-trie
@Language: C++
@Datetime: 16-02-09 05:53
*/

/**
 * Your Trie object will be instantiated and called as such:
 * Trie trie;
 * trie.insert("lintcode");
 * trie.search("lint"); will return false
 * trie.startsWith("lint"); will return true
 */
class TrieNode {
public:
    // Initialize your data structure here.
    static const int ALPHA = 27;    //26 is '\0'
    TrieNode * nodes[ALPHA];
    TrieNode() {
        for(int i=0;i<ALPHA;++i)
            nodes[i]=NULL;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    void insert(string word) {
        TrieNode *tn = root;
        for(int i=0;i<word.length();tn=tn->nodes[word[i]-'a'],++i)
            if (tn->nodes[word[i]-'a']==NULL)
                tn->nodes[word[i]-'a'] = new TrieNode();
        if (tn->nodes[TrieNode::ALPHA-1]==NULL)
            tn->nodes[TrieNode::ALPHA-1]= new TrieNode();
    }

    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode *tn = root;
        int i;
        for(i=0;i<word.length() && tn->nodes[word[i]-'a']
            ;tn=tn->nodes[word[i]-'a'],++i);
        if (i==word.length() && tn->nodes[TrieNode::ALPHA-1])
            return true;
        else
            return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *tn = root;
        int i;
        for(i=0;i<prefix.length() && tn->nodes[prefix[i]-'a']
            ;tn=tn->nodes[prefix[i]-'a'],++i);
        if (i==prefix.length())
            return true;
        else
            return false;
    }
    ~Trie(){
        destroy(root);
    }
private:
    TrieNode* root;
    void destroy(TrieNode *tn){
        if (tn==NULL)
            return;
        for(int i=0;i<TrieNode::ALPHA;++i)
            destroy(tn->nodes[i]);
        delete tn;
    }
};